#!/usr/bin/env python3

def heap_sort(array):
    for index in range(int((len(array) - 1)/2.0 - 0.5), -1, -1):
        heapify(array, len(array), index)

    for index in range(len(array) - 1, 0, -1):
        array[index], array[0] = array[0], array[index]
        heapify(array, index, 0)

def heapify(array, n, i):
    left = 2 * i + 1
    right = left + 1
    largest_index = i
    if left < n and array[largest_index] < array[left]:
        largest_index = left

    if right < n and array[largest_index] < array[right]:
        largest_index = right
        
    if largest_index != i:
        array[largest_index], array[i] = array[i], array[largest_index]
        if 2 * largest_index + 1 < n:
            heapify(array, n, largest_index)


if __name__ == '__main__':
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    heap_sort(array)
    print("array is " + str(array))
    array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    heap_sort(array)
    print("array is " + str(array))
    array = [2, 3, 1, 4, 7, 8, 9, 10, 6, 5]
    heap_sort(array)
    print("arra is " + str(array))
